\bigskip
{\magonebf 5.1 Directed graphs (graph)}

An instance $G$ of the data type $graph$ consists of a set of nodes $V$ and a 
set of edges E ($node$ and $edge$ are predefined data types). Every edge $e\in 
E$ is a pair of nodes $(v,w) \in V\times V$, $v$ is called the source of $e$ and
$w$ is called the target of $e$. With every node $v$ the list of its adjacent 
edges $adj\_list(v) = \{\ e \in E\ | source(e) = v\ \}$, called the adjacency 
list of $v$, is associated.

\bigskip
\def\name{$graph$}
\def\type{graph}
{\bf 1. Creation of a graph}

\create G {}

creates an instance $G$ of type $graph$ and initializes it to the
empty graph.


\bigskip
{\bf 2. \operations}

{\bf a) Access operations}
\+\cleartabs & \hskip 2truecm & \hskip 5.5truecm &\cr
\+\op int        indeg {node\ v}                     
                                      {returns the indegree of node $v$}
\smallskip
\+\op int        outdeg {node\ v}                     
                                      {returns the outdegree of node $v$}
\smallskip
\+\op node       source {edge\ e}               
                                      {returns the source node of edge $e$}
\smallskip
\+\op node       target {edge\ e}               
                                      {returns the target node of edge $e$}
\smallskip
\+\op int        number\_of\_nodes { }
                             {returns the number of nodes in $G$ }
\smallskip
\+\op int        number\_of\_edges { }
                             {returns the number of edges in $G$ }
\smallskip
\+\op list(node) all\_nodes {      }
                             {returns the list of all nodes of $G$}
\smallskip
\+\op list(edge) all\_edges {      }
                             {returns the list of all edges of $G$}
\smallskip
\+\op list(edge) adj\_edges {node\ v}  
                             {returns the list of all edges adjacent to $v$}
\smallskip
\+\op list(node) adj\_nodes {node\ v}  
                             {returns the list of all nodes adjacent to $v$}
\smallskip
\+\op edge   first\_adj\_edge {node\ v}
                           {returns the first edge in the adjacency list of $v$}
\smallskip 
\+\op edge   last\_adj\_edge {node\ v} 
                           {returns the last edge in the adjacency list of $v$}
\smallskip
\+\op edge   adj\_succ {edge\ e}           
                            {returns the successor of edge $e$ in the }
\+\nop                      {adjacency list of $source(e)$ }
\+\nop                      {(nil if it does not exist)}
\smallskip
\+\op edge   adj\_pred {edge\ e}          
                             {returns the predecessor of edge $e$ in the }
\+\nop                       {adjacency list of $source(e)$}
\+\nop                       {(nil if it does not exist)}
\smallskip
\+\op edge   cyclic\_adj\_succ {edge\ e}    
                             {returns the cyclic successor of edge $e$ in the}
\+\nop                       {adjacency list of $source(e)$}
\smallskip
\+\op edge   cyclic\_adj\_pred {edge\ e}    
                             {returns the cyclic predecessor of edge $e$ in the}
\+\nop                       {adjacency list of $source(e)$}
\smallskip
\+\op node   choose\_node   {}
                              {returns a node of $G$ (nil if $G$ is empty)}
\smallskip
\+\op edge   choose\_edge   {}
                              {returns an edge of $G$ (nil if $G$ is empty)}

\bigskip
{\bf b) Update operations}
\medskip
\+\op node   new\_node {}   
                             {adds a new node to $G$ and returns it}
\smallskip
\+\op void   del\_node {node\ v}      
                             {deletes $v$ and all edges adjacent to $v$}
\+\nop                       {from $G$. \precond{$indeg(v) = 0$}.}
\smallskip
\+\op edge   new\_edge {node\ v,\ w}
                             {adds a new edge $(v,w)$ to $G$ by appending }
\+\nop                       {it to the adjacency list of $v$ and returns it.}
\smallskip
\+\op edge   new\_edge {edge\ e,\ node\  w,\ rel\_pos\ dir=after} {}
\+\nop                      {adds a new edge $e\' = (source(e),w)$ to $G$ by }
\+\nop                      {inserting it after ($dir$=after) or before ($dir$}
\+\nop                      {=before) edge $e$ into the adjacency list of }
\+\nop                      {$source(e)$, returns $e\'$.}
\smallskip
\+\op void   del\_edge {edge\ e}      
                             {deletes the edge $e$ from $G$}
\smallskip
\+\op void       del\_all\_nodes {}
                             {deletes all nodes from $G$ }
\smallskip
\+\op void       del\_all\_edges {}
                             {deletes all edges from $G$ }
\smallskip
\+\op edge   rev\_edge {edge\ e}      
                             {reverses the edge $e = (v,w)$ by removing it }
\+\nop                       {from $G$ and inserting the edge $e\' = (w,v)$ }
\+\nop                       {into $G$ by appending it to the adjacency list}
\+\nop                       {of $w$, returns $e\'$ }
\smallskip
\+\op void   rev {}                 
                             {all edges in $G$ are reversed}
\smallskip
\+\op void   sort\_nodes {int (*cmp)(node\&,\ node\&)}  {}
\+\nop                       {the nodes of $G$ are sorted according to the}
\+\nop                       {ordering defined by the comparing function}
\+\nop                       {$cmp$. Subsequent executions of forall\_nodes}
\+\nop                       {step through the nodes in this order.}
\+\nop                       { (cf. TOPSORT1 in section 8.1)}
\smallskip
\+\op void   sort\_nodes {node\_array(T)\ A}  {}
\+\nop                       {the nodes of $G$ are sorted according to the}
\+\nop                       {entries of node\_array $A$ (cf. section 5.7)}
\+\nop                       {\precond $T$ must be linearly ordered}
\smallskip
\+\op void   sort\_edges {int (*cmp)(edge\&,\ edge\&)}  {}
\+\nop                       {the edges of $G$ are sorted according to the}
\+\nop                       {ordering defined by the comparing function}
\+\nop                       {$cmp$. Subsequent executions of forall\_edges}
\+\nop                       {step through the edges in this order.}
\+\nop                       { (cf. TOPSORT1 in section 8.1)}
\smallskip
\+\op void   sort\_edges {edge\_array(T)\ A}  {}
\+\nop                       {the edges of $G$ are sorted according to the}
\+\nop                       {entries of edge\_array $A$ (cf. section 5.7)}
\+\nop                       {\precond $T$ must be linearly ordered}
\smallskip
\+\op list(edge) insert\_reverse\_edges {} {}
\+\nop                       {for every edge $(v,w)$ in $G$ the reverse edge}
\+\nop                       {$(w,v)$ is inserted into $G$. The list of all}
\+\nop                       {inserted edges is returned.}
\+\op void   clear {}              
                             {makes $G$ the empty graph}

\bigskip
{\bf c) Iterators}
\medskip
With the adjacency list of every node $v$ is associated a list iterator 
called the adjacency iterator of $v$ (cf. list). There are operations to 
initialize the adjacency iterator, to move it to the successor or predecessor
list item, to access its contents (an edge) and to test if it is defined,
($\ne$ nil). Adjacency iterators are used to implement iteration statements 
(forall\_adj\_edges, forall\_adj\_nodes). 
\bigskip
\+\op void   init\_adj\_iterator {node\ v}         
                      {assigns nil to the adjacency iterator of node $v$}
\smallskip
\+\op bool   current\_adj\_edge {edge\&\ e,\ node\ v}  {}
\+\nop                {if the adjacency iterator of $v$ is defined ($\ne$ nil)} 
\+\nop                {its contents is assigned to $e$ and true is returned}
\+\nop                {else false is returned.}
\smallskip
\+\op bool   next\_adj\_edge {edge\&\ e,\ node\ v}     {}
\+\nop                {moves the adjacency iterator of $v$ forward (to the}
\+\nop                {first item of $adj\_list(v)$ if it is nil) and returns}
\+\nop                {$G$.current\_adj\_edge($e,v$)}
\smallskip
\+\op bool   current\_adj\_node {node\&\ w,\ node\ v}  {}
\+\nop                {if $G$.current\_adj\_edge($e$, $v$) = true then assign}
\+\nop                {$target(e)$ to w and return true, else return}
\+\nop                {false}
\smallskip
\+\op bool   next\_adj\_node {node\&\ w,\ node\ v}     {}
\+\nop                {if $G$.next\_adj\_edge($e$, $v$) = true then assign}
\+\nop                {$target(e)$ to w and return true, else return}
\+\nop                {false}
\smallskip
\+\op void   reset {}                          
                      {assign nil to all adjacency iterators in $G$}
\bigskip

\vfill\eject
{\bf d) Miscellaneous operations}
\medskip
\smallskip
\+\op void   write {string\ s}        
                             {writes a compressed representation of $G$ to }
\+\nop                       {the file with name $s$}
\smallskip
\+\op void   read {string\ s}         
                             {read a compressed representation of $G$ from }
\+\nop                       {the file with name $s$}
\smallskip
\+\op void   print\_node {node\ v,\ ostream\ O = cout} {}              
\+\nop                       {writes a readable representation of node $v$ to }
\+\nop                       {the output stream $O$}
\smallskip
\+\op void   print\_edge {edge\ e,\ ostream\ O = cout} {}              
\+\nop                       {writes a readable representation of edge $e$ to}
\+\nop                       {the output stream $O$}
\smallskip
\+\op void   print {ostream\ O = cout}              
                             {writes a readable representation of $G$ to the}
\+\nop                       {output stream $O$}
\smallskip

\bigskip
{\bf e) Operators}

\+\opb graph\& = G1        
                             {makes a copy of $G1$ and assigns it to $G$.}


\bigskip
{\bf 3. Iteration}


{\bf forall\_nodes}($v,G$) 
$\{$ ``the nodes of $G$ are successively assigned to $v$" $\}$

{\bf forall\_edges}($e,G$)  
$\{$ ``the edges of $G$ are successively assigned to $e$" $\}$

{\bf forall\_adj\_edges}($e,w$) \nl
\phantom{{\bf forall\_edges}($v,G$)}
$\{$ ``the edges adjacent to node w are successively assigned to e" $\}$

{\bf forall\_adj\_nodes}($v,w$) \nl  
\phantom{{\bf forall\_edges}($v,G$)}
$\{$ ``the nodes adjacent to node w are successively assigned to v" $\}$

\bigskip
{\bf 4. Implementation}

Graphs are implemented by adjacency lists. Most operations take constant
time, except of all\_nodes, all\_edges, del\_all\_nodes, del\_all\_edges,
clear, write, and read which take time $O(n+m)$, where $n$ is the current
number of nodes and $m$ is the current number of edges. The space requirement
is $O(n+m)$.


\bigskip
{\bf 5. Examples}

See section 8.1.

\vfill\eject
